// https://leetcode.cn/problems/maximum-units-on-a-truck/
// Created by ade on 2022/11/15.
//
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maximumUnits(vector <vector<int>> &boxTypes, int truckSize) {
        sort(boxTypes.begin(), boxTypes.end(), [=](vector<int> &a, vector<int> &b) {
            return a[1] > b[1];
        });
        int sum = 0;
        for (int i = 0; i < boxTypes.size(); i++) {
            if (truckSize == 0) break;
            if (boxTypes[i][0] < truckSize) {
                sum += boxTypes[i][0] * boxTypes[i][1];
                truckSize -= boxTypes[i][0];
            } else if (boxTypes[i][0] == truckSize) {
                sum += boxTypes[i][0] * boxTypes[i][1];
                break;
            } else {
                sum += truckSize * boxTypes[i][1];
                truckSize = 0;
            }
        }
        return sum;
    }
};

int main() {
    Solution so;
    vector <vector<int>> nums = {{1, 3},
                                 {2, 2},
                                 {3, 1}};
    cout << so.maximumUnits(nums, 4) << endl;
    return 0;
}